\chapter{Combinatorial}

\section{Permutations}
	% \subsection{Factorial}
		% \import{factorial.tex}

	\subsection{Cycles}
		Let $g_S(n)$ be the number of $n$-permutations whose cycle lengths all belong to the set $S$. Then
		$$\sum_{n=0} ^\infty g_S(n) \frac{x^n}{n!} = \exp\left(\sum_{n\in S} \frac{x^n} {n} \right)$$

	% \subsection{Derangements}
	% 	Permutations of a set such that none of the elements appear in their original position.
	% 	\[ \mkern-2mu D(n) = (n-1)(D(n-1)+D(n-2)) = n D(n-1)+(-1)^n = \left\lfloor\frac{n!}{e}\right\rceil \]

	\subsection{Burnside's lemma} % https://open.kattis.com/problems/littletoys
		Given a group $G$ of symmetries and a set $X$, the number of elements of $X$ \emph{up to symmetry} equals
		 \[ {\frac {1}{|G|}}\sum _{{g\in G}}|X^{g}|, \]
		 where $X^{g}$ are the elements fixed by $g$ ($g.x = x$).

		 If $f(n)$ counts ``configurations'' (of some sort) of length $n$, we can ignore rotational symmetry using $G = \mathbb Z_n$ to get
		 \[ g(n) = \frac 1 n \sum_{k=0}^{n-1}{f(\text{gcd}(n, k))} = \frac 1 n \sum_{k|n}{f(k)\phi(n/k)}. \]

	% \kactlimport{IntPerm.h}
	% \kactlimport{PermGroup.h}

\section{Partitions and subsets}
	\subsection{Partition function}
		Number of ways of writing $n$ as a sum of positive integers, disregarding the order of the summands.
		\[ p(0) = 1,\ p(n) = \sum_{k \in \mathbb Z \setminus \{0\}}{(-1)^{k+1} p(n - k(3k-1) / 2)} \]
		\[ p(n) \sim 0.145 / n \cdot \exp(2.56 \sqrt{n}) \]

		\begin{center}
		\begin{tabular}{c|c@{\ }c@{\ }c@{\ }c@{\ }c@{\ }c@{\ }c@{\ }c@{\ }c@{\ }c@{\ }c@{\ }c@{\ }c}
			$n$    & 0 & 1 & 2 & 3 & 4 & 5 & 6  & 7  & 8  & 9  & 20  & 50  & 100 \\ \hline
			$p(n)$ & 1 & 1 & 2 & 3 & 5 & 7 & 11 & 15 & 22 & 30 & 627 & $\mathtt{\sim}$2e5 & $\mathtt{\sim}$2e8 \\
		\end{tabular}
		\end{center}

	\subsection{Lucas' Theorem}
		Let $n,m$ be non-negative integers and $p$ a prime. Write $n=n_kp^k+...+n_1p+n_0$ and $m=m_kp^k+...+m_1p+m_0$. Then $\binom{n}{m} \equiv \prod_{i=0}^k\binom{n_i}{m_i} \pmod{p}$.

\section{General purpose numbers}
	\subsection{Bernoulli numbers}
		EGF of Bernoulli numbers is $B(t)=\frac{t}{e^t-1}$ (FFT-able).
		$B[0,\ldots] = [1, -\frac{1}{2}, \frac{1}{6}, 0, -\frac{1}{30}, 0, \frac{1}{42}, \ldots]$

		Sums of powers:
		\small
		\[ \sum_{i=1}^n i^m = \frac{1}{m+1} \sum_{k=0}^m \binom{m+1}{k} B_k (n+1)^{m+1-k} \]
		\normalsize

		Euler-Maclaurin formula for infinite sums:
		\small
		\[ \sum_{i=m}^{\infty} f(i) = \int_m^\infty f(x) dx - \sum_{k=1}^\infty \frac{B_k}{k!}f^{(k-1)}(m) \]
		\[ \approx \int_{m}^\infty f(x)dx + \frac{f(m)}{2} - \frac{f'(m)}{12} + \frac{f'''(m)}{720} + O(f^{(5)}(m)) \]
		\normalsize

	\subsection{Stirling numbers of the first kind}
		Number of permutations on $n$ items with $k$ cycles.
		\begin{align*}
			&c(n,k) = c(n-1,k-1) + (n-1) c(n-1,k),\ c(0,0) = 1 \\
			&\textstyle \sum_{k=0}^n c(n,k)x^k = x(x+1) \dots (x+n-1)
		\end{align*}
		$c(8,k) = 8, 0, 5040, 13068, 13132, 6769, 1960, 322, 28, 1$ \\
		$c(n,2) = 0, 0, 1, 3, 11, 50, 274, 1764, 13068, 109584, \dots$

	\subsection{Eulerian numbers}
		Number of permutations $\pi \in S_n$ in which exactly $k$ elements are greater than the previous element. $k$ $j$:s s.t. $\pi(j)>\pi(j+1)$, $k+1$ $j$:s s.t. $\pi(j)\geq j$, $k$ $j$:s s.t. $\pi(j)>j$.
		$$E(n,k) = (n-k)E(n-1,k-1) + (k+1)E(n-1,k)$$
		$$E(n,0) = E(n,n-1) = 1$$
		$$E(n,k) = \sum_{j=0}^k(-1)^j\binom{n+1}{j}(k+1-j)^n$$

	\subsection{Stirling numbers of the second kind}
		Partitions of $n$ distinct elements into exactly $k$ groups.
		$$S(n,k) = S(n-1,k-1) + k S(n-1,k)$$
		$$S(n,1) = S(n,n) = 1$$
		$$S(n,k) = \frac{1}{k!}\sum_{j=0}^k (-1)^{k-j}\binom{k}{j}j^n$$

	\subsection{Bell numbers}
		Total number of partitions of $n$ distinct elements. $B(n) =$
		$1, 1, 2, 5, 15, 52, 203, 877, 4140, 21147, \dots$. For $p$ prime,
		\[ B(p^m+n)\equiv mB(n)+B(n+1) \pmod{p} \]

	\subsection{Labeled unrooted trees}
		\# on $n$ vertices: $n^{n-2}$ \\
		\# on $k$ existing trees of size $n_i$: $n_1n_2\cdots n_k n^{k-2}$ \\
		\# with degrees $d_i$: $(n-2)! / ((d_1-1)! \cdots (d_n-1)!)$
		% https://cp-algorithms.com/graph/pruefer_code.html
		% https://math.stackexchange.com/questions/2550064/proof-of-generalized-cayleys-formula
		% https://codeforces.com/group/KIrM1Owd8u/contest/258080/problem/E

	\subsection{Catalan numbers}
		\[ C_n=\frac{1}{n+1}\binom{2n}{n}= \binom{2n}{n}-\binom{2n}{n+1} = \frac{(2n)!}{(n+1)!n!} \]
		\[ C_0=1,\ C_{n+1} = \frac{2(2n+1)}{n+2}C_n,\ C_{n+1}=\sum C_iC_{n-i} \]
		${C_n = 1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, \dots}$
		\begin{itemize}[noitemsep]
			\item sub-diagonal monotone paths in an $n\times n$ grid.
			\item strings with $n$ pairs of parenthesis, correctly nested.
			\item binary trees with with $n+1$ leaves (0 or 2 children).
			\item ordered trees with $n+1$ vertices.
			\item ways a convex polygon with $n+2$ sides can be cut into triangles by connecting vertices with straight lines.
			\item permutations of $[n]$ with no 3-term increasing subseq.
		\end{itemize}

\section{Young Tableaux}

Let a \textbf{Young diagram} have shape $\lambda=(\lambda_1\geq \cdots\geq \lambda_k),$ where $\lambda_i$ equals the number of cells in the $i$-th (left-justified) row from the top. A \textbf{Young tableau} of shape $\lambda$ is a filling of the $n=\sum \lambda_i$ cells with a permutation of $1\ldots n$ such that each row and  column is increasing.

\textbf{Hook-Length Formula}: For the cell in position $(i,j)$, let $h_\lambda(i,j)=\left|\{(I,J)|i\le I, j\le J, (I=i\text{ or }J=j)\}\right|.$ The number of Young tableaux of shape $\lambda$ is equal to
$f^\lambda \ =\ \frac{n!}{\prod h_\lambda (i,j)}.$

\textbf{Schensted's Algorithm}: converts a permutation $\sigma$ of length $n$ into a pair of Young Tableaux $(S(\sigma),T(\sigma))$ of the same shape. When inserting $x=\sigma_i$,

\begin{enumerate}
\item Add $x$ to the first row of $S$ by inserting $x$ in place of the largest $y$ with $x<y$. If $y$ doesn't exist, push $x$ to the end of the row, set the value of $T$ at that position to be $i$, and stop.
\item Add $y$ to the second row using the same rule, keep repeating as necessary.
\end{enumerate}

\begin{comment}
For $\sigma=(5,2,3,1,4),$
$$S(\sigma): \begin{array}{c}
5
\end{array}\to \begin{array}{c}
2 \\ 
5
\end{array}\to \begin{array}{cc}
2 & 3 \\ 
5
\end{array}\to \begin{array}{cc}
1 & 3 \\ 
2 \\
5
\end{array}\to \begin{array}{ccc}
1 & 3 & 4\\ 
2 \\
5
\end{array}$$
$$T(\sigma): \begin{array}{c}
1
\end{array}\to \begin{array}{c}
1 \\ 
2
\end{array}\to \begin{array}{cc}
1 & 3 \\ 
2
\end{array}\to \begin{array}{cc}
1 & 3 \\ 
2 \\
4
\end{array}\to \begin{array}{ccc}
1 & 3 & 5\\ 
2 \\
4
\end{array}$$
\end{comment}

All pairs $(S(\sigma),T(\sigma))$ of the same shape correspond to a unique $\sigma$, so
$n!=\sum (f^{\lambda})^2.$ Also, $S(\sigma^R)=S(\sigma)^T.$

Let $d_k(\sigma),a_k(\sigma)$ be the lengths of the longest subseqs which are a union of $k$ decreasing/ascending subseqs, respectively. Then $a_k(\sigma)=\sum_{i=1}^k\lambda_i, d_k(\sigma)=\sum_{i=1}^k\lambda^*_i,$ where $\lambda^*_i$ is size of the $i$-th column. 

% 300iq Disjoint LIS
% msg camp 2014 "sequence shape"

	% \kactlimport{RSK.h}
	% \kactlimport{RSKrecover.h}

\section{Other}
	\kactlimport{DeBruijnSeq.h}
	\kactlimport{NimProduct.h}
	\kactlimport{MatroidIsect.h}